USACO 2024 US Open Contest, Bronze

[USACO24OPEN] Logical Moos B

题目描述

Farmer John 有一个布尔语句，包含 $N$ 个关键字（$1\le N<2\cdot {10}^5$，$N$ 为奇数）。奇数位置仅出现 $\mathtt{\text{true}}$ 或 $\mathtt{\text{false}}$，偶数位置上仅出现 $\mathtt{\text{and}}$ 或 $\mathtt{\text{or}}$。

一个 $x\mathrm{OPERATOR}y$ 形式的短语，其中 $x$ 和 $y$ 为 $\mathtt{\text{true}}$ 或 $\mathtt{\text{false}}$，而 $\mathrm{OPERATOR}$ 为 $\mathtt{\text{and}}$ 或 $\mathtt{\text{or}}$ ，按如下规则求值：

• $x\mathrm{and}y$：如果 $x$ 和 $y$ 均为 $\mathtt{\text{true}}$，则求值结果为 $\mathtt{\text{true}}$，否则为 $\mathtt{\text{false}}$。
• $x\mathrm{or}y$：如果 $x$ 或 $y$ 为 $\mathtt{\text{true}}$，则求值结果为 $\mathtt{\text{true}}$，否则为 $\mathtt{\text{false}}$。

在求值该语句时，FJ 必须考虑 Moo 语言中的运算符优先级。与 C++ 类似，$\mathrm{and}$ 优先级高于 $\mathrm{or}$。更具体地说，在求值该语句时，重复以下步骤直至该语句仅包含一个关键字。

1. 如果语句中包含 $\mathrm{and}$，选择其中任意一个，并将其周围的短语替换为其求值结果。
2. 否则，该语句包含 $\mathrm{or}$。选择其中任意一个，并将其周围的短语替换为其求值结果。

可以证明，如果在指定的一个步骤中可以求值多个短语，那么选择哪一个求值并不重要；该语句最终的求值结果将始终相同。

FJ 有 $Q$（$1\le Q\le 2\cdot {10}^5$）个询问。在每个询问中，他给你两个整数 $l$ 和 $r$（$1\le l\le r\le N$，$l$ 和 $r$ 均为奇数），并删除关键字 $l$ 到关键字 $r$ 之间的段。反过来，他希望用一个简单的 $\mathtt{\text{true}}$ 或 $\mathtt{\text{false}}$ 替换他刚刚删除的段，以使整个语句的求值结果为某个指定的布尔值。帮助 FJ 判断是否可行！

输入格式

输入的第一行包含 $N$ 和 $Q$。

下一行包含 $N$ 个字符串，为一个合法的布尔语句。

以下 $Q$ 行，每行包含两个整数 $l$ 和 $r$，以及一个字符串 $\mathtt{\text{true}}$ 或 $\mathtt{\text{false}}$，表示他希望整个语句的求值结果为 $\mathtt{\text{true}}$ 还是 $\mathtt{\text{false}}$。

输出格式

输出一个长度为 $Q$ 的字符串，其中如果第 $i$ 个询问的结果为可能，则第 $i$ 个字符为 Y，否则为 N。

样例 #1

样例输入 #1

5 7
false and true or true
1 1 false
1 3 true
1 5 false
3 3 true
3 3 false
5 5 false
5 5 true

样例输出 #1

NYYYNYY

样例 #2

样例输入 #2

13 4
false or true and false and false and true or true and false
1 5 false
3 11 true
3 11 false
13 13 true

样例输出 #2

YNYY

提示

样例解释 1

我们来分析第一个询问：

如果我们删除段 $[1,1]$ 并替换为 $\mathtt{\text{true}}$，那么整个语句将变为：

$\mathtt{\text{true and true or true}}$

我们对位置 $2$ 处的 $\mathtt{\text{and}}$

关键字求值，得到

$\mathtt{\text{true or true}}$

由于我们没有剩下的 $\mathtt{\text{and}}$ 关键字，我们必须求值 $\mathtt{\text{or}}$ 关键字。求值结束后，余下的是

$\mathtt{\text{true}}$

可以证明，如果我们用 $\mathtt{\text{false}}$ 替换该段，该语句仍将求值为 $\mathtt{\text{true}}$，因此我们输出 N，因为该语句不可能求值为 false。

对于第二个询问，我们可以将段 $[1,3]$ 替换为 true，整个语句将求值为 $\mathtt{\text{true}}$，因此我们输出 Y。

对于第三个询问，由于 $[1,5]$ 是整个语句，我们可以将其替换为任意内容，因此我们输出 Y。

测试点性质

• 测试点 $3-5$：$N,Q\le {10}^2$。
• 测试点 $6-8$：$N,Q\le {10}^3$。
• 测试点 $9-26$：没有额外限制。

参考答案

/*
算法分析
初始化和读取输入：首先，代码读取布尔语句的长度 n 和查询的数量 q，然后读取布尔语句中的每个关键字，并将其存储在字符串向量 s 中。

分组：代码通过遍历布尔语句，将每个 true 或 false 关键字分配到一个组中。每个 "or" 关键字标志着一个新的组的开始。

记录 false 和 true 的位置：代码遍历每个组，记录每个组中第一个和最后一个 false 关键字的位置，以及整个语句中第一个和最后一个 true 组的位置。

处理查询：对于每个查询，代码检查查询段是否与整个语句的评估结果冲突。如果整个语句已经确定为 true 或 false，则可以直接回答查询。否则，代码检查查询段是否包含必要的 false 或 true 关键字，以满足查询的期望结果。

输出结果：对于每个查询，代码输出 Y 或 N，表示是否可以通过替换查询段来达到期望的布尔值。

时间复杂度
初始化和读取输入：O(n)
分组：O(n)
记录 false 和 true 的位置：O(n)
处理查询：对于每个查询，检查和比较操作的时间复杂度为 O(1)，因此总的时间复杂度为 O(q)。
总体时间复杂度为 O(n + q)。
*/
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9; // 定义一个很大的数，用于初始化 first_false 和 last_false

int main(){
    cin.tie(0) -> sync_with_stdio(0); // 关闭 C++ 的 IO 同步，提高 IO 效率
    int n, q; cin >> n >> q; // 读取关键字数量 n 和查询数量 q
    vector<string> s(n); // 创建一个字符串向量，存储布尔语句中的每个关键字
    for(int i = 0; i < n; i++) cin >> s[i]; // 读取布尔语句中的每个关键字

    vector<int> group(n); // 创建一个整数向量，存储每个关键字所属的组号
    int group_no = 0; // 初始化组号
    for(int i = 0; i < n; i++){
        if(s[i] == "or"){ // 如果关键字是 "or"，则增加组号
            group_no++;
        }
        else{
            if(i % 2 == 0){ // 如果关键字位于奇数位置（即 true 或 false）
                group[i] = group_no; // 将当前组号赋值给该关键字
            }
        }
    }

    vector<int> first_false(group_no + 1, INF); // 创建一个整数向量，存储每个组的第一个 false 索引
    vector<int> last_false(group_no + 1, -1); // 创建一个整数向量，存储每个组的最后一个 false 索引
    for(int i = 0; i < n; i += 2){ // 遍历每个 true 或 false 关键字
        int g = group[i]; // 获取当前关键字的组号
        if(s[i] == "false"){ // 如果当前关键字是 false
            if(first_false[g] == INF){ // 如果该组还没有记录第一个 false
                first_false[g] = i; // 记录第一个 false 的索引
            }
            last_false[g] = i; // 更新最后一个 false 的索引
        }
    }

    int total_first_true = INF, total_last_true = -1; // 存储整个语句中第一个和最后一个 true 关键字的组号
    for(int i = 0; i <= group_no; i++){
        if(first_false[i] == INF){ // 如果该组没有 false
            if(total_first_true == INF){ // 如果还没有找到第一个 true 组
                total_first_true = i; // 记录第一个 true 组
            }
            total_last_true = i; // 更新最后一个 true 组
        }
    }

    while(q--){ // 处理每个查询
        int l, r; cin >> l >> r; // 读取查询的开始和结束位置
        --l; --r; // 将位置从 1-based 转换为 0-based
        string t; cin >> t; // 读取查询期望的结果
        int l_group = group[l], r_group = group[r]; // 获取查询段的开始和结束组号

        // 如果整个语句为 true，只需要一个 true 组即可
        if(total_first_true < l_group || total_last_true > r_group){
            cout << (t == "true" ? 'Y' : 'N'); // 如果查询期望的结果与整个语句的结果一致，则输出 Y，否则 N
            continue;
        }
        if(t == "true"){
            // 如果查询期望的结果为 true，检查查询段是否包含第一个 false 或最后一个 false
            cout << (first_false[l_group] < l || last_false[r_group] > r ? 'N' : 'Y');
        }
        else{
            cout << 'Y'; // 如果查询期望的结果为 false，且查询段不包含整个语句的唯一 true 组，则输出 Y
        }
    }
}

[USACO24OPEN] Walking Along a Fence B

题目描述

Farmer John 的 $N$ 头奶牛（$1\le N\le {10}^5$）每头都喜欢日常沿围着牧场的栅栏散步。

栅栏由 $P$ 根柱子组成（$4\le P\le 2\cdot {10}^5$，$P$ 为偶数），每根柱子的位置是 FJ 农场地图上的一个不同的二维坐标点 $(x,y)$（$0\le x,y\le 1000$）。每根柱子通过垂直或水平线段的栅栏连接到两根相邻的柱子，因此整个栅栏可以被视为各边平行于 $x$ 轴或 $y$ 轴的一个多边形（最后一根柱子连回第一根柱子，确保围栏形成一个包围牧场的闭环）。栅栏多边形是「规则的」，体现在栅栏段仅可能在其端点处重合，每根柱子恰好属于两个栅栏段，同时每两个在端点处相交的栅栏段都是垂直的。

每头奶牛的日常散步都有一个偏好的起始和结束位置，均为沿栅栏的某个点（可能在柱子处，也可能不在）。每头奶牛日常散步时沿着栅栏行走，从起始位置开始，到结束位置结束。由于栅栏形成闭环，奶牛有两条路线可以选择。由于奶牛是一种有点懒的生物，每头奶牛都会选择距离较短的方向沿栅栏行走（如果并列，奶牛可以选择任一方向）。

求每头奶牛行走的距离。

输入格式

输入的第一行包含 $N$ 和 $P$。以下 $P$ 行的每一行包含两个整数，以顺时针或逆时针顺序表示栅栏柱子的位置。以下 $N$ 行的每一行包含四个整数 $x_1{y}_1{x}_2{y}_2$，表示一头奶牛的起始位置 $(x_1,y_1)$ 和结束位置 $(x_2,y_2)$。

输出格式

输出 $N$ 个整数，为每头奶牛行走的距离。

样例 #1

样例输入 #1

5 4
0 0
2 0
2 2
0 2
0 0 0 2
0 2 1 0
2 1 0 2
1 0 1 2
1 2 1 0

样例输出 #1

2
3
3
4
4

提示

样例解释

第一头奶牛可以直接从 $(0,0)$ 走到 $(0,2)$。

第二头奶牛可以从 $(0,2)$ 走到 $(0,0)$，然后走到 $(1,0)$。

第四头奶牛有两条长度相等的可能路线：$(1,0)\to (0,0)\to (0,2)\to (1,2)$ 和 $(1,0)\to (2,0)\to (2,2)\to (1,2)$。

测试点性质

• 测试点 $2-6$：$0\le x,y\le 100$ 且 $N\le 100$。
• 测试点 $7-11$：没有额外限制。

参考答案

/*
1.栅栏长度的最大值:
	栅栏的长度最大为 1000，因为数据范围限制，坐标系中只有这么多个整数点，即栅栏上最多只有 1000000个点
2.遍历栅栏统计距离:
	程序从第一个点开始，按顺序“走”一遍栅栏，并在沿途中统计按这个顺序(这个顺序取决于输入中点给出的顺序)从第一个点到栅栏上每一个点的距离。
3.定义两个距离变量:
	dis1:按给定顺序从(x1,y1)走到(x2,y2)的距离。
	dis2:按另一个顺序从(x1,y1)走到(x2,y2)的距离。
4.计算 dis2:
	dis2等于栅栏长度减去 dis1。
5.计算 dis1:
	dis1可以利用类似于前缀和的思路，用从第一个点到(x2,y2)的距离减去从第一个点到(x1,y1)的距离，得到从(x1,y1)走到(x2,y2)的距离。
	注意:这个值可能是负数，所以要取绝对值。
6.最终答案:
	取dis1和 dis2的最小值即可得到答案。
*/

#include<iostream>
using namespace std;

int n, p, dis[1005][1005]; // n为奶牛数量，p为栅栏柱子数量，dis为记录每个点沿栅栏的距离的二维数组
struct { int x, y; } ps[(int)2e5+5]; // 定义结构体存储栅栏柱子的坐标，并预留足够的空间

// 辅助函数，返回整数x的符号，正数返回1，负数返回-1，零返回0
int sign(int x) { return x > 0 ? 1 : -1; }

// 辅助函数，返回整数x的绝对值，如果x为负则返回其正值，否则返回x
int abs_(int x) { return x > 0 ? x : -x; }

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // 关闭C++的IO同步，提高IO效率
    cin >> n >> p; // 读取奶牛数量n和栅栏柱子数量p
    for (int i = 1; i <= p; i++) cin >> ps[i].x >> ps[i].y; // 读取每个栅栏柱子的坐标
    ps[p + 1] = ps[1]; // 将第一个点复制到数组末尾，实现闭环

    // 遍历栅栏柱子，更新dis数组
    for (int i = 2; i <= p + 1; i++) {
        if (ps[i].x == ps[i - 1].x) { // 如果两个连续点在同一垂直线上
            int s = sign(ps[i].y - ps[i - 1].y); // 确定是向上还是向下
            for (int j = ps[i - 1].y + s; j != ps[i].y + s; j += s) { // 遍历这两点之间的所有点
                dis[ps[i].x][j] = dis[ps[i].x][j - s] + 1; // 更新dis数组
            }
        }
        if (ps[i].y == ps[i - 1].y) { // 如果两个连续点在同一水平线上
            int s = sign(ps[i].x - ps[i - 1].x); // 确定是向左还是向右
            for (int j = ps[i - 1].x + s; j != ps[i].x + s; j += s) { // 遍历这两点之间的所有点
                dis[j][ps[i].y] = dis[j - s][ps[i].y] + 1; // 更新dis数组
            }
        }
//        cout<< "========================================"<<endl;
//   		for(int i2=0;i2<5;i2++){
//    		for(int j2=0;j2<5;j2++){
//    			cout<<dis[i2][j2]<<" ";
//			}
//			cout<<endl;
//		}
//  cout<< "========================================"<<endl;
    }
    

    int x0 = ps[1].x, y0 = ps[1].y; // 第一个栅栏柱子的坐标，用作栅栏起点
    int x1, y1, x2, y2, dis1, dis2; // 用于存储奶牛起始点和终点的坐标，以及计算的距离
    while (n--) { // 处理每头奶牛的查询
        cin >> x1 >> y1 >> x2 >> y2; // 读取奶牛的起始点和终点坐标
        dis1 = abs_(dis[x1][y1] - dis[x2][y2]); // 计算从起始点到终点沿栅栏的距离
        dis2 = dis[x0][y0] - dis1; // 计算从终点到起始点沿栅栏的距离（栅栏总长减去第一距离）
        cout << min(dis1, dis2) << endl; // 输出两个方向中较短的距离
    }
    return 0;
}

[USACO24OPEN] Farmer John's Favorite Permutation B

题目描述

Farmer John 有一个长为 $N$（$2\le N\le {10}^5$）的排列 $p$，包含从 $1$ 到 $N$ 的每个正整数恰好一次。然而，Farmer Nhoj 闯入了 FJ 的牛棚并拆散了 $p$。为了不至于太过残忍，FN 写了一些能够帮助 FJ 重建 $p$ 的提示。当 $p$ 中剩余多于一个元素时，FN 会执行以下操作：

令 $p$ 的剩余元素为 $p_1^{\prime },p_2^{\prime },\dots ,p_n^{\prime }$，

• 如果 $p_1^{\prime }>p_n^{\prime }$，他写下 $p_2^{\prime }$ 并从排列中删除 $p_1^{\prime }$。
• 否则，他写下 $p_{n-1}^{\prime }$ 并从排列中删除 $p_n^{\prime }$。

最终，Farmer Nhoj 将按顺序写下 $N-1$ 个整数 $h_1,h_2,\dots ,h_{N-1}$。给定 $h$，Farmer John 希望得到你的帮助重建与 Farmer Nhoj 的提示相一致的最小字典序 $p$，或者判断 Farmer Nhoj 一定犯了错误。我们知道，给定两个排列 $p$ 和 $p^{\prime }$，如果在第一个两者不同的位置 $i$ 处有 $p_i<p_i^{\prime }$，则 $p$ 的字典序小于 $p^{\prime }$。

输入格式

每个测试点包含 $T$ 个独立的测试用例（$1\le T\le 10$）。每个测试用例的描述如下：

第一行包含 $N$。

第二行包含 $N-1$ 个整数 $h_1,h_2,\dots ,h_{N-1}$（$1\le h_i\le N$）。

输出格式

输出 $T$ 行，每个测试用例一行。

如果存在与 $h$ 相一致的 $1\dots N$ 的排列 $p$，输出字典顺序最小的 $p$。如果不存在这样的 $p$，输出 $-1$。

样例 #1

样例输入 #1

5
2
1
2
2
4
1 1 1
4
2 1 1
4
3 2 1

样例输出 #1

1 2
-1
-1
3 1 2 4
1 2 3 4

提示

对于第四个测试用例，如果 $p=[3,1,2,4]$ 则 FN 将写下 $h=[2,1,1]$。

p' = [3,1,2,4]
p_1' < p_n' -> h_1 = 2
p' = [3,1,2]
p_1' > p_n' -> h_2 = 1
p' = [1,2]
p_1' < p_n' -> h_3 = 1
p' = [1]

注意排列 $p=[4,2,1,3]$ 也会产生同样的 $h$，但 $[3,1,2,4]$ 字典序更小。

对于第二个测试用例，不存在与 $h$ 相一致的 $p$；$p=[1,2]$ 和 $p=[2,1]$ 均会产生 $h=[1]$，并非 $h=[2]$。

测试点性质

• 测试点 $2$：$N\le 8$。
• 测试点 $3-6$：$N\le 100$。
• 测试点 $7-11$：没有额外限制。

参考答案

/*
题解：https://www.luogu.com.cn/problem/solution/P10276

*/
#include<bits/stdc++.h>
using namespace std;
int h[100005];
int v[100005];
int a[100005];
bool in[100005];
void mian(){
	memset(v,0,sizeof v);
	memset(in,0,sizeof in);memset(a,0,sizeof a);memset(h,0,sizeof h);
	int n;cin>>n;
	for(int i=1;i<=n-1;i++){
		cin>>h[i];
		v[h[i]]++;
	}
	if(h[n-1]!=1){
		cout<<-1<<endl;return;
	}
	int x1=0,x2=0;
	for(int i=1;i<=n;i++){
		if(v[i]==0){
			if(x1)x2=i;
			else x1=i;
		}if(v[i]>1&&i>1||v[i]>2){
			cout<<-1<<endl;return;
		}
	}
	if(x1>x2)swap(x1,x2);
	if(x1==0)x1=1;
	int l=1,r=n;
	a[l]=x1;a[r]=x2;
	in[x1]=in[x2]=1;
	int nw=1;
	for(int i=3;i<=n;i++){//这里的 i 是目前填第几个数 
		if(a[l]>a[r]){
			while(in[h[nw]])nw++;
			a[++l]=h[nw];
			in[h[nw]]=1;
		}else{
			while(in[h[nw]])nw++;
			a[--r]=h[nw];
			in[h[nw]]=1;
		}
	}
	for(int i=1;i<=n;i++)cout<<a[i]<<" ";cout<<endl;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t;cin>>t;
	while(t--)mian(); 
	return 0;
}